#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode
{
  ListNode<T>* next;
  T val;
  ListNode(const T& v = T())
    :val(v),next(nullptr)
  {}
};

template<class T>
class SeqList
{
public:
  SeqList()
    :phead(nullptr)
  {}
  void push_back(const T& x)
  {
    ListNode<T>* newnode = new ListNode<T>(x);
    if(phead == nullptr)
    {
      phead = newnode;
    }
    else
    {
       ListNode<T>* tail = phead;
       while(tail->next)
       {
          tail = tail->next;
       }
       tail->next = newnode;
    }
  }
  void push_front(const  T& x)
  {
    ListNode<T>* newnode = new ListNode<T>(x);
    newnode->next = phead;
    phead = newnode;
  } 
  void pop_back()
  {
    assert(phead!=nullptr);
    if(phead->next == nullptr) //只有一个节点
    {
      delete phead ;
      phead = nullptr;
    }
    //多个节点
    ListNode<T>* tail = phead;
    ListNode<T>* prev = nullptr;
    while(tail->next!=nullptr)
    {
      prev = tail;
      tail= tail->next;
    }
    delete tail;
    tail = nullptr;
    prev->next = nullptr;
  }
  void pop_front()
  {
    assert(phead);
    ListNode<T>* del = phead;
    phead = phead->next;
    delete del;
  }
  void Print()
  {
    ListNode<T>* cur = phead;
    while(cur)
    {
      cout << cur->val << " ";
      cur = cur->next;
    }
    cout << endl;
  }


  ListNode<T>* findNode(const T& x)
  {
    return _findNode(phead,x);
  }

  ListNode<T>* _findNode(ListNode<T>* phead,const T& x) //从phead位置开始找第一个值为x的节点,返回地址
  {
    ListNode<T>* cur = phead;
    while(cur)
    {
      if(cur->val == x)
      {
        return cur;
      }
      cur = cur->next;
    }
    cout <<" 查找"<<x<<"失败,返回nullptr...."<<endl;
    return nullptr;
  }

  //如果想查找全部值为x的位置
  //ListNode<T>* pos = findNode(phead,x);
  //while(pos)
  //{
  //  cout << pos<<endl;
  //  pos = findNode(pos,x);
  //}

  void push_after_pos(ListNode<T>* pos,const T& x) //在pos后面插入
  {
    assert(pos);
    ListNode<T>* newnode = new ListNode<T>(x);
    ListNode<T>* next = pos->next;
    //pos newnode next 
    pos->next = newnode;
    newnode->next = next;
  }

  void push_front_pos(ListNode<T>* pos ,const T& x) //在pos前插入 
  {
    assert(pos);
    ListNode<T>* newnode = new ListNode<T>(x);
    if(phead ->next == nullptr)
    {
      newnode->next = phead;
      phead = newnode;
      return ;
    }
    ListNode<T>* prev = phead;
    while(prev->next != pos)
    {
      prev = prev->next;
    }
    //prev newnode pos
    prev->next = newnode;
    newnode->next = pos;
  }

  void erase_pos(ListNode<T>* pos)
  {
    assert(pos);
    if(pos == phead) //要删除的是头结点
    {
      ListNode<T>* del = phead;
      phead = phead->next;
      delete del;
      return ;
    }
    ListNode<T>* prev = phead; 
    while(prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    delete pos;
  }

  void erase_after_pos(ListNode<T>* pos)
  {
    assert(pos);
    assert(pos->next);//pos不能是尾节点
    ListNode<T>* del = pos->next;
    pos->next = del->next;
    delete del;
  }
  
  ~SeqList()
  {
    ListNode<T>* cur = phead;
    while(cur)
    {
      ListNode<T>* next = cur->next;
      delete cur;
      cur = next;
    }
  }
private:
  ListNode<T>* phead; //头指针
};
